package com.algorithm.cjm.july.chapter1.ch1;

/**
 * 旋转字符串
 *
 * @Author: Jie Ming Chen
 * @Date: 2019-04-23
 * @Version 1.0
 */
public class RotateString {
    static RotateString object = new RotateString();

    public static void main(String[] args) {
        String abcxyz = object.leftRotateString2("abcxyz", 2);
        System.out.println(abcxyz);
    }

    /**
     * 暴力移位法
     * 时间复杂度 O(m*n)  空间复杂度 O(1)
     *
     * @param target 目标字符串
     * @param m 需要旋转字符串的位数
     * @return
     */
    private String leftRotateString1(String target, int m) {
        char[] chars = target.toCharArray();
        while (m-- > 0) {
            leftShiftOne(chars, target.length());
        }
        return new String(chars);
    }

    /**
     * 左移一个字符
     *
     * @param arr
     * @param n
     */
    private void leftShiftOne(char[] arr, int n) {
        // 保存第一个字符
        char t = arr[0];
        for (int i = 1; i < n; i++) {
            arr[i-1] = arr[i];
        }
        arr[n - 1] = t;
    }

    /**
     * 三步反转法
     * 一分为二, 第一个部分为需要旋转的，先对拆分后的代码进行反转，然后再对两个拆分的反转。一共反转三次
     * 例如 target: abcxyz  拆分成 t1=abc t2=xyz  t1^T=cba t2^T=zyx  (t1^Tt2^T)^T= xyzabc
     * 满足字符串旋转三位的条件
     *
     * 时间复杂度O(n),空间复杂度O(1)
     *
     * @param target
     * @param m
     */
    public String leftRotateString2(String target, int m) {
        char[] array = target.toCharArray();
        int n = target.length();
        //若要左移动大于n位，那么和%n 是等价的
        m %= n;
        reverseString(array, 0, m - 1);
        reverseString(array, m, n - 1);
        reverseString(array, 0, n - 1);
        return new String(array);
    }

    /**
     * 选择字符串
     *
     * @param arr
     * @param start
     * @param end
     */
    private void reverseString(char[] arr, int start, int end) {
        while (start < end) {
            char tmp = arr[start];
            arr[start++] = arr[end];
            arr[end--] = tmp;
        }
    }
}
